template <typename Type>
struct Node
{
	Type data;
	Node<Type>* next;
};

template <typename Type>
class SinglyLinkedList
{
public:
	SinglyLinkedList();
	SinglyLinkedList(Type a[], int length);
	int Length();
	Type SearchByPosition(int position);
	int SearchByValue(Type value);
	Type Insert(int position, Type value);
	Type Delete(int position);
	void PrintList();
	~SinglyLinkedList();
private:
	Node<Type>* first;
};

template <typename Type>
SinglyLinkedList<Type>::SinglyLinkedList()
{
	first = new Node<Type>;
	first->next = NULL;
}

//头插法建立链表
template <typename Type>
SinglyLinkedList<Type>::SinglyLinkedList(Type a[], int length)
{
	first = new Node<Type>;
	first->next = NULL;
	for (int i = 0; i < length; i++)
	{
		Node<Type>* tmp = new Node<Type>;
		tmp->data = a[i];
		tmp->next = first->next;
		first->next = tmp;
	}
}

//尾插法建立链表
template <typename Type>
SinglyLinkedList<Type>::SinglyLinkedList(Type a[], int length)
{
	first = new Node<Type>;
	first->next = NULL;
	Node<Type>* p = first;
	for (int i = 0; i < length; i++)
	{
		Node<Type>* tmp = new Node<Type>;
		tmp->data = a[i];
		tmp->next = NULL;
		p->next = tmp;
		p = tmp;
	}
}

template <typename Type>
int SinglyLinkedList<Type>::Length()
{
	int count = 0;
	Node<Type>* p = first->next;
	while (p != NULL)
	{
		p = p->next;
		count++;
	}
	return count;
}

template <typename Type>
Type SinglyLinkedList<Type>::SearchByPosition(int position)
{
	int count = 1;
	Node<Type>* p = first->next;
	while (p != NULL && count < position)
	{
		p = p->next;
		count++;
	}

	if (p == NULL)
	{
		//用Type型data的默认值或系统初始值作为回调参数
		return ;
	}
	else
	{
		return p->data;
	}
}

template <typename Type>
int SinglyLinkedList<Type>::SearchByValue(Type value)
{
	int count = 1;
	Node<Type>* p = first->next;
	while (p != NULL)
	{
		if (p->data == value)
		{
			return count;
		}
		p = p->next;
		count++;
	}
	return 0;
}

template <typename Type>
Type SinglyLinkedList<Type>::Insert(int position, Type value)
{
	int count = 1;
	Node<Type>* p = first->next;
	while (p != NULL && count < position)
	{
		p = p->next;
		count++;
	}

	if (p == NULL)
	{
		//用Type型data的默认值或系统初始值作为回调参数
		return ;
	}
	else
	{
		Node<Type>* tmp = new Node<Type>;
		tmp->data = value;
		tmp->next = p->next;
		p->next = tmp;
		return tmp->data;
	}
}

template <typename Type>
Type SinglyLinkedList<Type>::Delete(int position)
{
	int count = 1;
	Node<Type>* p = first->next;
	while (p != NULL && count < position - 1)
	{
		p = p->next;
		count++;
	}

	if (p == NULL || p->next == NULL)
	{
		//用Type型data的默认值或系统初始值作为回调参数
		return ;
	}
	else
	{
		//删除为危险操作，需要二次确认
		bool flg;
		cout << "是否删除！！？（0、否；1、是）：";
		cin >> flg;

		if (flg)
		{
			Node<Type>* tmp = p->next;
			Type x = tmp->data;
			p->next = tmp->next;
			delete tmp;
			return x;
		}
		else
		{
			cout << "删除取消" << endl;
		}
	}
}

template <typename Type>
void SinglyLinkedList<Type>::PrintList()
{
	int count = 1;
	Node<Type>* p = first->next;
	while (p != NULL)
	{
		cout << "第" << count << "个节点存储的信息为：" << p->data << endl;
		p = p->next;
		count++;
	}
}

template <typename Type>
SinglyLinkedList<Type>::~SinglyLinkedList()
{
	while (first != NULL)
	{
		Node<Type>* p = first;
		first = first->next;
		delete p;
	}
}